package com.peng.tree.serialization;

import com.peng.tree.Node;

import java.util.LinkedList;
import java.util.Queue;

public class WidthSerAndDeSer {
    public static Queue<String> serialize(Node head) {
        if (head == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        Queue<String> ans = new LinkedList<>();
        queue.add(head);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            if (cur == null) {
                ans.add(null);
                continue;
            }
            ans.add(String.valueOf(cur.value));
            queue.add(cur.left);
            queue.add(cur.right);
        }
        return ans;
    }

    public static Node deserialize(Queue<String> nodes) {
        String rootVal = nodes.poll();
        if (rootVal == null) {
            return null;
        }

        Queue<Node> queue = new LinkedList<>();
        Node root = generateNode(rootVal);
        queue.add(root);

        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            Node left = generateNode(nodes.poll());
            Node right = generateNode(nodes.poll());
            if (left != null) {
                cur.left = left;
                queue.add(left);
            }
            if (right != null) {
                cur.right = right;
                queue.add(right);
            }

        }

        return root;


    }

    public static Node generateNode(String val) {
        return val == null ? null : new Node(Integer.parseInt(val));
    }


    public static void main(String[] args) {
        Node node = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);

        node.left = node2;
        node.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node4.left = node8;
        node4.right = node9;
        /*
                   1
             2              3
           4    5         6     7
         8   9

         */
        Queue<String> queue = serialize(node);
        System.out.println(queue);

        Node deserialize = deserialize(queue);
        System.out.println(deserialize);


    }
}
